﻿#define _CRT_SECURE_NO_WARNINGS
//86.
//给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
//
//在「杨辉三角」中，每个数是它左上方和右上方的数的和。

int** generate(int numRows, int* returnSize, int** returnColumnSizes) {
    int i = 0;
    // 开辟存放杨辉三⻆的⼆维数组
    int** arr = (int**)malloc(numRows * sizeof(int*));
    // 为每⼀维分配内存
    for (i = 0; i < numRows; i++) {
        arr[i] = (int*)malloc(numRows * sizeof(int));
    }
    // 更新⾏数
    *returnSize = numRows;
    // 存放每⼀⾏数据的个数
    *returnColumnSizes = (int*)malloc(numRows * sizeof(int));

    // 按⾏从上到下遍历
    for (i = 0; i < numRows; i++) {
        int j = 0;
        // 更新每⼀⾏的元素个数
        (*returnColumnSizes)[i] = i + 1;
        arr[i][0] = arr[i][i] = 1;

        // 更新中间元素，遍历前两维时不会进⼊循环，不需要特判
        for (j = 1; j < i; j++) {
            arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
        }
    }
    // 返回杨辉三⻆
    return arr;
}